检索结果

Select

1. 基于顶点冲突学习的最大公共子图算法

王宇, 刘燕丽, 陈劭武

计算机应用 2021, 41 (6): 1756-1760. DOI: 10.11772/j.issn.1001-9081.2020091381

摘要（407）

PDF （962KB）（502）

针对最大公共子图（MCS）的传统分支策略依赖于图的静态属性，缺少学习历史搜索信息的问题，提出了基于顶点冲突学习的分支策略。首先，把上界的减少值作为分支点完成匹配动作的奖励；其次，由于当最优解被更新时，得到的最优解是分支点不断推理产生的结果，因此给予在完整的搜索路径上的分支点适当的奖励，从而强化这些顶点对搜索的积极作用；最后，设计了匹配动作的价值函数，并选择具有最大累计奖励的顶点作为新的分支点。在McSplit算法基础上，提出了糅合新分支策略的McSplitRLR算法。实验结果表明，除去均可以被所有对比算法在10 s之内解决的简单算例，在相同机器和求解限制时间条件下，相较当前先进的算法McSplit、McSplitSBS，McSplitRLR分别多解决了109、33个困难算例，求解率分别提高了5.6%、1.6%。

参考文献 | 相关文章 | 多维度评价

Select

2. 基于动态奖惩的分支策略的SAT完备算法

刘燕丽, 徐振兴, 熊丹

计算机应用 2017, 37 (12): 3487-3492. DOI: 10.11772/j.issn.1001-9081.2017.12.3487

摘要（429）

PDF （911KB）（525）

针对学习子句数量有限或相似度高导致历史信息有限、搜索树不平衡的问题，提出了基于动态奖惩的分支策略。首先，对每次单子句传播的变元进行惩罚，依据变元是否产生冲突和产生冲突的间隔，确立不同的惩罚函数；其次，在学习阶段，利用学习子句确定对构造冲突有益的变元，非线性增加它们的活跃度；最后，选择活跃度最大的变元作为新分支变元。在glucose3.0算法基础上，完成了改进的动态奖惩算法——AP7。实验结果表明，相比glucose3.0算法，AP7算法的剪枝率提高了14.2%~29.3%，少数算例剪枝率的提高可达51%，且改进后的AP7算法相比glucose3.0算法，运行时间缩短了7%以上。所提分支策略可以有效降低搜索树规模，使搜索树更加平衡，减少计算时间。

参考文献 | 相关文章 | 多维度评价

Select

3. 高动态环境下结合频谱校正的长周期伪码捕获

庞统张天骐刘燕丽杜晓华

计算机应用 2010, 30 (8): 2214-2217.

摘要（334）

PDF （553KB）（997）

针对基于快速傅里叶变换（FFT）的伪码捕获过程中出现的能量泄漏和扇贝损失，通过对一种基于分段匹配滤波—快速傅里叶变换（PMF-FFT）的伪码捕获方法的分析，提出了使用频谱校正的方法来解决这些问题。对FFT后的功率谱最大值进行频谱校正后，提高了最大幅值，同时抑制了旁瓣的干扰，得到了更为精确的多普勒频偏，这样就能获得更高的检测概率。同时给出了基于该算法的信号模型和理论分析的表达式，在理论分析的基础上，使用计算机进行仿真，证明该方法有良好的捕获效果。